public class 完成旅途的最少时间 {
    //和谷歌二面的题目非常相似
    //https://leetcode.cn/problems/minimum-time-to-complete-trips/description/
    
    public long minimumTime(int[] arr, int m) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            min = Math.min(arr[i],min);
        }
        long l = 0;
        long r = (long)min * m;
        long ret = 0;
        long mid = 0;
        while (l <= r){
            mid = (l + r) >> 1;
            if(f(arr,mid) >= m){
                ret = mid;
                r = mid - 1;
            }else{
                l = mid + 1;
            }
        }
        return ret;
    }

    private static long f(int[] arr, long mid) {
        long sum = 0;
        for(int num : arr){
            sum += (mid / num);
        }
        return sum;
    }
}
